#include <iostream>
#include <set>
#include <math.h> 
#include <algorithm>

#define ll long long

using namespace std;

int main(){
	int t;
	cin >> t;
	
	for(int i = 0;i < t; ++i){
		ll n;
		cin >> n;
		n *= 2;
		ll s1 = 0,s2 = 0;
		set<ll> a,b;
		for(int j = 0; j < n; ++j){
			ll num;
			cin >> num;
			if(j % 2 == 0){
				s1 += num;
				a.insert(num);
			}else{
				s2 += num;
				b.insert(num);
			}
		}
		if(n == 2){
			cout << min(s1,s2);
			continue;
		}
		
		ll diff = abs(s1 - s2);
		if(diff == 0 || diff == 1){
			cout << min(s1,s2);
			continue;
		}
		
		ll temp = 0;
		diff /= 2;
		if(s1 > s2){
			for(ll v : a){
				ll k = v - diff;
				if(k >= 1){
					auto it = upper_bound(b.begin(),b.end(),k);
					--it;
					temp = max(s2 + v - *it,temp);
				}
			}
		}else{
			for(ll v : b){
				ll k = v - diff;
				auto it = upper_bound(a.begin(),a.end(),k);
				if(it == a.begin()){
					continue;
				}
				--it;
				temp = max(s1 + v - *it,temp);
			}
		}
		
		cout << temp;
		
	}
	
	
	return 0;
}
